

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=auto>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon.png">
  <link rel="icon" href="/img/favicon.png">
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=5.0, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="author" content="Cheney">
  <meta name="keywords" content="Coding">
  
    <meta name="description" content="计算控制疫情所需要的最少时间">
<meta property="og:type" content="article">
<meta property="og:title" content="洛谷P048疫情控制">
<meta property="og:url" content="https://cheney822.gitee.io/2020/12/01/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%AF%BE%E8%AE%BE--%E6%B4%9B%E8%B0%B7P048%E7%96%AB%E6%83%85%E6%8E%A7%E5%88%B6/index.html">
<meta property="og:site_name" content="Cheney blog">
<meta property="og:description" content="计算控制疫情所需要的最少时间">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/f80d5df01ca048368fc32d87c98e6db5.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/c3f7a259b4ff434382d35516705bf890.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/caf9cd5807cc481ea656315f97609189.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/29a254a29b45451fbb4470172556e58c.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/f99dd72c39aa4f589b017ec6b75e5778.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/f83e55e02ccc4b839986d21374f2dd41.png">
<meta property="article:published_time" content="2020-12-01T05:14:00.000Z">
<meta property="article:modified_time" content="2022-04-05T13:14:27.743Z">
<meta property="article:author" content="Cheney">
<meta property="article:tag" content="算法">
<meta property="article:tag" content="C++">
<meta property="article:tag" content="洛谷">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="https://imgbed.cheney.cc/picgo/f80d5df01ca048368fc32d87c98e6db5.png">
  
  
  <title>洛谷P048疫情控制 - Cheney blog</title>

  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap@4/dist/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/github-markdown-css@4/github-markdown.min.css" />
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hint.css@2/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@10/styles/github-gist.min.css" />
    
  

  
    <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3/dist/jquery.fancybox.min.css" />
  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_ba1fz6golrf.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_lbnruvf0jn.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script id="fluid-configs">
    var Fluid = window.Fluid || {};
    var CONFIG = {"hostname":"cheney822.gitee.io","root":"/","version":"1.8.14","typing":{"enable":true,"typeSpeed":70,"cursorChar":"_","loop":false},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"right","visible":"hover","icon":""},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"copy_btn":true,"image_zoom":{"enable":true,"img_url_replace":["",""]},"toc":{"enable":true,"headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":1},"lazyload":{"enable":true,"loading_img":"/img/loading.gif","onlypost":false,"offset_factor":2},"web_analytics":{"enable":false,"baidu":null,"google":null,"gtag":null,"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null,"path":"window.location.pathname","ignore_local":false}},"search_path":"/local-search.xml"};
  </script>
  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.4.1"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand" href="/">
      <strong>Cheney Blog</strong>
    </a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" target="_self" href="javascript:;" data-toggle="modal" data-target="#modalSearch" aria-label="Search">
              &nbsp;<i class="iconfont icon-search"></i>&nbsp;
            </a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" target="_self" href="javascript:;" aria-label="Color Toggle">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner" id="banner" parallax=true
         style="background: url('https://imgbed.cheney.cc/Blog_config/default.png') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="page-header text-center fade-in-up">
            <span class="h2" id="subtitle" title="洛谷P048疫情控制">
              
            </span>

            
              <div class="mt-3">
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2020-12-01 13:14" pubdate>
        2020年12月1日 下午
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      6.5k 字
    </span>
  

  
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      33 分钟
    </span>
  

  
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid nopadding-x">
  <div class="row nomargin-x">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-x-md">
      <div class="container nopadding-x-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto">
            <!-- SEO header -->
            <h1 style="display: none">洛谷P048疫情控制</h1>
            
            <div class="markdown-body">
              <p><a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P1084">洛谷P1084</a></p>
<h1 id="一、问题描述："><a href="#一、问题描述：" class="headerlink" title="一、问题描述："></a>一、问题描述：</h1><p>设计目的：深入理解树。<br><strong>内容：</strong><br>H 国有 n 个城市，这 n 个城市用 n-1 条双向道路相互连通构成一棵树，1 号城市是首都，<br>也是树中的根节点。<br>H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。<br>但特别要注意的是，首都是不能建立检查点的。现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。请问最少需要多少个小时才能控制情。注意：不同的军队可以同时移动。<br><strong>输入格式</strong><br>第一行一个整数 n，表示城市个数。<br>接下来的 n-1 行，每行 3 个整数，u,v,w，每两个整数之间用一个空格隔开，表示从城市 u<br>到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树，且根节点编号为 1。<br>接下来一行一个整数 m，表示军队个数。<br>接下来一行 m 个整数，每两个整数之间用一个空格隔开，分别表示这 m 个军队所驻扎的城市的编号。<br><strong>输出格式</strong><br>一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。
 </p>
<h1 id="二、需求分析："><a href="#二、需求分析：" class="headerlink" title="二、需求分析："></a>二、需求分析：</h1><p>若一个时间限制满足题意，则所有比它大的时间限制一定都满足题意，因此本题答案具有单调性，可以二分答案求解。接下来的重点就是check函数，如何判断一个时间限制符不符合条件呢？显然，对于所有军队，我们希望它最后停留的节点深度越小越好，这样可以控制最多的路径。因此我们让所有的军队尽量地向上走，若一个军队可以走到根节点，则令其暂时停在根节点的子节点；否则走到时间限制内能够走到的深度最小的节点。这个步骤可以用树上倍增进行优化。</p>
<p>经过这步处理后，我们先找出所有以根节点的子节点为根的子树中，是否有到叶子节点的路径还未被驻扎，并记录下还有路径未被驻扎的这些子树的根节点。对于这些节点，可以证明，若该节点上停留有军队，则剩余时间最小的军队驻扎在该节点一定是最优的。这样处理过这些节点后，把剩下的节点按照到根节点的距离从小到大排序。<br>最后可能还会有一些军队未确定最后的驻扎节点，把这些军队按照剩余时间从小到大排序，然后和上一步处理出来的这些节点一一进行匹配。这是一个可以证明正确性的贪心策略。若所有未被驻扎的节点都有军队驻扎，则说明当前的时间限制可行；反之则不可行。</p>
<h1 id="三、概要设计："><a href="#三、概要设计：" class="headerlink" title="三、概要设计："></a>三、概要设计：</h1><h2 id="1、数据结构定义："><a href="#1、数据结构定义：" class="headerlink" title="1、数据结构定义："></a>1、数据结构定义：</h2><figure class="highlight cpp"><table><tr><td class="gutter"><div class="code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></div></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-type">int</span> n;<span class="hljs-comment">//城市个数</span><br><span class="hljs-type">int</span> m;<span class="hljs-comment">//军队个数</span><br><span class="hljs-type">int</span> TotalLength = <span class="hljs-number">0</span>;<span class="hljs-comment">//所有路径的长度之和</span><br><span class="hljs-type">int</span> T;<span class="hljs-comment">//f数组和dist数组第二维下标的最大值</span><br><span class="hljs-type">int</span> Depths[MAXSIZE];<span class="hljs-comment">//每个节点的深度，</span><br><span class="hljs-type">int</span> ArmyLoc[MAXSIZE];<span class="hljs-comment">//分别表示这 m 个军队所驻扎的城市的编号</span><br><span class="hljs-type">bool</span> Stayed[MAXSIZE];<span class="hljs-comment">//有无军队驻扎</span><br><span class="hljs-type">int</span> F_Num[MAXSIZE][<span class="hljs-number">20</span>];<span class="hljs-comment">//	存储i节点的第 2^j个祖先的节点编号</span><br><span class="hljs-type">int</span> F_length[MAXSIZE][<span class="hljs-number">20</span>];<span class="hljs-comment">//存储i节点到第 2^j个祖先的长度</span><br><span class="hljs-type">bool</span> need_dfs[MAXSIZE];<span class="hljs-comment">//根节点的子节点 是否需要被驻扎</span><br><span class="hljs-type">int</span> LeftTime[MAXSIZE];<span class="hljs-comment">// 处理过后仍闲置的军队,只储存剩余时间,不需要存当前停留的位置</span><br><span class="hljs-type">int</span> need_last[MAXSIZE];<span class="hljs-comment">//仍需要被驻扎的节点只存储节点到根节点的距离，不必存储节点编号</span><br>pair&lt;<span class="hljs-type">int</span>, <span class="hljs-type">int</span>&gt; FreeArmy[MAXSIZE];<span class="hljs-comment">//第一维存储该军队到达根节点后剩余的时间，第二维存储该军队当前所在的节点编号，存储的是能上升的根节点的闲置节点</span><br>queue&lt;<span class="hljs-type">int</span>&gt; que;<span class="hljs-comment">//倍增时用到的队列</span><br><br><span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> <span class="hljs-title class_">LinkList</span><br>&#123;<br>    <span class="hljs-type">int</span> Data = <span class="hljs-number">-999</span>;<br>    <span class="hljs-type">int</span> Power = <span class="hljs-number">-999</span>;<br>    LinkList* next = <span class="hljs-literal">NULL</span>;<br>&#125;LinkList;<br>LinkList* CCListHead[MAXSIZE];<span class="hljs-comment">//邻接表用来存储图</span><br></code></pre></td></tr></table></figure>

<h2 id="2、模块设计："><a href="#2、模块设计：" class="headerlink" title="2、模块设计："></a>2、模块设计：</h2><p>程序分为以下几个模块：</p>
<ul>
<li>MakeCountryGroup();//构建图</li>
<li>PreTreatment();//树上倍增预处理</li>
<li>Check()//检查当前的时间限制是否满足要求</li>
<li>IS_Controled(int x)//dfs序寻找路径未被驻扎的叶子节点</li>
</ul>
<h2 id="3、各模块间的调用关系："><a href="#3、各模块间的调用关系：" class="headerlink" title="3、各模块间的调用关系："></a>3、各模块间的调用关系：</h2><p> <img src="https://imgbed.cheney.cc/picgo/f80d5df01ca048368fc32d87c98e6db5.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<h1 id="四、详细设计"><a href="#四、详细设计" class="headerlink" title="四、详细设计"></a>四、详细设计</h1><p>主要算法：<br>1.读入树的信息并用存储图的方式（邻接表）储存（无向图）：MakeCountryGroup();<br>其中：CCListHead[i]为头的链表上节点的值表示与i节点有连接的节点编号<br>由于是无向图，每条边要正反存两次。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><code class="hljs cpp">cout &lt;&lt; <span class="hljs-string">&quot;请输入边的信息\n&quot;</span>;<br>   <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">1</span>; i &lt; n; i++)<br>   &#123;<br>       <span class="hljs-type">int</span> x, y, z;<br>       cin &gt;&gt; x &gt;&gt; y &gt;&gt; z;<br>     <br>       <span class="hljs-keyword">for</span> (Current = CCListHead[x]; Current-&gt;Data != <span class="hljs-number">-999</span>;) &#123;<br>           <span class="hljs-keyword">if</span> (Current-&gt;next== <span class="hljs-literal">NULL</span>)Current-&gt;next = <span class="hljs-keyword">new</span> LinkList;<br>           <span class="hljs-keyword">else</span> Current = Current-&gt;next;<br>       &#125;<br>       <span class="hljs-keyword">if</span> (Current == <span class="hljs-literal">NULL</span>)Current = <span class="hljs-keyword">new</span> LinkList;<br>       Current-&gt;Data = y;<br>       Current-&gt;Power = z;<br>       <span class="hljs-keyword">for</span> (Current = CCListHead[y]; Current-&gt;Data != <span class="hljs-number">-999</span>;) &#123;<br>           <span class="hljs-keyword">if</span> (Current-&gt;next == <span class="hljs-literal">NULL</span>)Current-&gt;next = <span class="hljs-keyword">new</span> LinkList;<br>           <span class="hljs-keyword">else</span> Current = Current-&gt;next;<br>       &#125;<br>       <span class="hljs-keyword">if</span> (Current == <span class="hljs-literal">NULL</span>)Current = <span class="hljs-keyword">new</span> LinkList;<br>       Current-&gt;Data = x;<br>       Current-&gt;Power = z;<br>       TotalLength += z;<span class="hljs-comment">//统计所有边的长度之和</span><br>   &#125;<br></code></pre></td></tr></table></figure>


<p>2：树上倍增预处理：PreTreatment();<br>计算出所有节点的第2^i个祖先的编号以及到他的距离<br>int F_Num[N][20];// 存储i节点的第 2^j个祖先的节点编号<br>int F_length[N][20];//存储i节点到第 2^j个祖先的长度<br>计算过程用到以下推导公式;<br>F_Num[i][j]=f[f[i][j-1]][j-1];<br>F_length[i][j]=dist[i][j-1]+dist[f[i][j-1]][j-1];<br>具体过程：建立一个空队列，并将根节点入队，同时存储根节点的深度为一<br>取出队头，遍历所有与其有连接的边。由于存储的时候是按照无向图存储，因此判定某个点是否是其父节点，对于连接到它父亲节点的边，直接跳过即可。记当前路径的另一端节点为 y，处理出 y的 depth、 F_Num、 F_Num三个数组的值，然后将 y入队。<br>不断重复第2步，直到队列为空。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-function"><span class="hljs-type">bool</span> <span class="hljs-title">IS_Controled</span><span class="hljs-params">(<span class="hljs-type">int</span> x)</span><span class="hljs-comment">//dfs序寻找路径未被驻扎的叶子节点</span></span><br><span class="hljs-function"></span>&#123;<br>    <span class="hljs-type">bool</span> IsLeaf = <span class="hljs-number">1</span>;<span class="hljs-comment">//用于判断是否是叶子节点</span><br>    <span class="hljs-keyword">if</span> (Stayed[x])<br>        <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;<span class="hljs-comment">//遇到已驻扎节点，直接返回1</span><br>    LinkList* Current1 = <span class="hljs-keyword">new</span> LinkList;<br>    <span class="hljs-keyword">for</span> (Current1 = CCListHead[x]; Current1-&gt;Data != <span class="hljs-number">-999</span>;)<br>    &#123;<br>        <span class="hljs-type">int</span> y = Current1-&gt;Data;<br>        <span class="hljs-keyword">if</span> (Depths[y] &lt; Depths[x]) &#123;<br><br>            <span class="hljs-keyword">if</span> (Current1-&gt;next == <span class="hljs-literal">NULL</span>)<span class="hljs-keyword">break</span>;<br>            <span class="hljs-keyword">else</span> Current1 = Current1-&gt;next;<br><br>            <span class="hljs-keyword">continue</span>;<span class="hljs-comment">//遇到连接父节点的边时continue</span><br>        &#125;<br>            <br>        IsLeaf = <span class="hljs-number">0</span>; <span class="hljs-comment">//只要有一条不是连接着父节点的边，说明不是叶子节点</span><br>        <span class="hljs-keyword">if</span> (!<span class="hljs-built_in">IS_Controled</span>(y))<span class="hljs-comment">//递归，如果子节点未被控制，返回0 //若某个子节点搜索时遇到路径未被驻扎的叶子节点，直接返回0</span><br>            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>        <span class="hljs-keyword">if</span> (Current1-&gt;next == <span class="hljs-literal">NULL</span>)<span class="hljs-keyword">break</span>;<br>        <span class="hljs-keyword">else</span> Current1 = Current1-&gt;next;<br>    &#125;<br>    <span class="hljs-keyword">if</span> (IsLeaf)<span class="hljs-comment">//当前节点是叶子节点且未被驻扎</span><br>        <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>    <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;<span class="hljs-comment">//叶子节点均被控制，返回1</span><br>&#125;<br></code></pre></td></tr></table></figure>


<p>3：二分结果<br>由于最终的答案一定介于0和所有边的权值之和之间，则取区间【L，R】L=0,R=权值之和，mid=L+R/2，判断疫情在mid时间之内能否控制（具体判断方法后面会给出），如果能则说明时间可以进一步缩短，让L=mid缩小范围继续判断，并记录此时的mid为答案，后续不断刷新答案。如果不能说明给的时间不够，则R=mid进一步判断。直到L不再小于R为止，最终得到的答案即为所求。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-type">int</span> Left = <span class="hljs-number">0</span>, Right = TotalLength, Mid;<br>    <span class="hljs-type">int</span> Answer = <span class="hljs-number">-1</span>;<span class="hljs-comment">//程序结果</span><br>    <span class="hljs-keyword">while</span> (Left &lt;= Right)<br>    &#123;<br>        Mid = (Left + Right)/<span class="hljs-number">2</span>;<br>        <span class="hljs-keyword">if</span> (<span class="hljs-built_in">Check</span>(Mid))<span class="hljs-comment">//当前的时间限制满足题意，则更新答案</span><br>            Right = Mid - <span class="hljs-number">1</span>, Answer = Mid;<br>        <span class="hljs-keyword">else</span> <span class="hljs-comment">//二分扩大时间继续判断</span><br>            Left = Mid + <span class="hljs-number">1</span>;<br>    &#125;<br></code></pre></td></tr></table></figure>



<p>下面是检查疫情能否在给定时间得到控制的具体方法，即Check函数的具体实现：</p>
<p>流程图：<br> <img src="https://imgbed.cheney.cc/picgo/c3f7a259b4ff434382d35516705bf890.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p>4：上移军队并存储闲置军队<br>将军队上移到根节点的子节点或者能够达到的最浅节点后，若该军队还能向上到达根节点，说明它还有转移到其它子树去驻扎的可能，因此将它记为暂时闲置，用一个二元组存储起来；否则就将该军队驻扎在当前节点，并将当前节点标记为已驻扎。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">1</span>; i &lt;= m; i++)<br>   &#123;<br>       <span class="hljs-type">int</span> x = ArmyLoc[i];<span class="hljs-comment">//第i个军队所在的城市</span><br>       <span class="hljs-type">int</span> cnt = <span class="hljs-number">0</span>;<span class="hljs-comment">//cnt统计时间花费</span><br>       <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> j = T; j &gt;= <span class="hljs-number">0</span>; j--)<br>           <span class="hljs-keyword">if</span> (F_Num[x][j] &gt; <span class="hljs-number">1</span> &amp;&amp; cnt + F_length[x][j] &lt;= lim)<br>               <span class="hljs-comment">//若终点在根节点之前且不会超过时限</span><br>           &#123;<br>               cnt += F_length[x][j];<br>               x = F_Num[x][j];<br>           &#125;<br>       <span class="hljs-keyword">if</span> (F_Num[x][<span class="hljs-number">0</span>] == <span class="hljs-number">1</span> &amp;&amp; cnt + F_length[x][<span class="hljs-number">0</span>] &lt;= lim) &#123;<span class="hljs-comment">//若当前节点为根节点的子节点且该军队可以在时限内到达根节点</span><br>           cnt_h++; <span class="hljs-comment">//存储的是能上升的根节点的闲置节点</span><br>           FreeArmy[cnt_h].first = lim - cnt - F_length[x][<span class="hljs-number">0</span>];<span class="hljs-comment">//第一维存储该军队到达根节点后剩余的时间，</span><br>           FreeArmy[cnt_h].second = x;<span class="hljs-comment">//第二维存储该军队当前所在的节点编号</span><br>       &#125;<br>       <span class="hljs-keyword">else</span><br>           Stayed[x] = <span class="hljs-number">1</span>;<span class="hljs-comment">//将该军队驻扎在当前节点，并将当前节点标记为已驻扎。</span><br>   &#125;<br></code></pre></td></tr></table></figure>



<p>5：dfs寻找路径未被驻扎的叶子节点：IS_Controled(int x)<br>从每个根节点的子节点开始搜索，若搜索时遇到已驻扎节点，则返回1；<br>若一直搜索到某个叶子（除了与父亲节点相连的边之外没有其他边）节点都没有遇到已驻扎节点，则说明根节点的这个子节点需要军队驻扎，返回0。<br>如果当前不是叶子节点并且当前节点的子节点均被控制，也返回1。<br>当遇到连接父节点的边时，continue即可。<br>dfs序查找结束后，存储根节点的需要被驻扎的子节点。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-keyword">for</span> (Current = CCListHead[<span class="hljs-number">1</span>]; Current-&gt;Data != <span class="hljs-number">-999</span>;) &#123;<br>       <span class="hljs-keyword">if</span> (!<span class="hljs-built_in">IS_Controled</span>(Current-&gt;Data)) <span class="hljs-comment">//dfs寻找路径未被驻扎的叶子节点</span><br>           need_dfs[Current-&gt;Data] = <span class="hljs-number">1</span>;<span class="hljs-comment">//dfs查找结束后，存储需要根节点的需要被驻扎的子节点。</span><br>       <span class="hljs-keyword">if</span> (Current-&gt;next == <span class="hljs-literal">NULL</span>)<span class="hljs-keyword">break</span>;<br>       <span class="hljs-keyword">else</span> Current = Current-&gt;next;<br>   &#125;<br></code></pre></td></tr></table></figure>


<p>6： 对根节点的需要被驻扎的子节点进行初步处理<br>对于任意一个需要被驻扎的节点，若它上面停留着一支不能到达根节点并返回该节点的军队，则令其驻扎在该节点；另外的，因为一个节点只需要一支军队驻扎，因此我们在这里选择剩余时间最小的节点。所以在处理前要先将 h数组按照剩余时间从小到大排序。<br>对于处理过后仍闲置的军队，将它们的剩余时间存储起来，只要存储剩余时间就好。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-built_in">sort</span>(FreeArmy + <span class="hljs-number">1</span>, FreeArmy + cnt_h + <span class="hljs-number">1</span>);<span class="hljs-comment">//军队到达根后剩余时间从小到大排序</span><br>  <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">1</span>; i &lt;= cnt_h; i++)&#123;<span class="hljs-comment">//需要被驻扎的节点，若上面停留着一支军队不能到达根并返回，则令其驻扎在该节点；  </span><br>      <span class="hljs-keyword">if</span> (need_dfs[FreeArmy[i].second] &amp;&amp; FreeArmy[i].first &lt; F_length[FreeArmy[i].second][<span class="hljs-number">0</span>])<br>          need_dfs[FreeArmy[i].second] = <span class="hljs-number">0</span>;<span class="hljs-comment">//去除标记</span><br>      <span class="hljs-keyword">else</span> <span class="hljs-comment">//对于处理过后仍闲置的军队，将它们的剩余时间存储起来备用。</span><br>          LeftTime[++LeftArmy] = FreeArmy[i].first;<br> &#125;<br></code></pre></td></tr></table></figure>

<ol start="7">
<li>找到仍需要被驻扎的节点并存储<br>经过第6步的初步处理，可能还有一些节点需要被驻扎，此时遍历一遍根节点的子节点，找到这些节点并存储起来。与第6步相同，这里只要存储节点到根节点的距离就可以了，不必存储节点编号。</li>
</ol>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-keyword">for</span> (Current = CCListHead[<span class="hljs-number">1</span>]; Current-&gt;Data != <span class="hljs-number">-999</span>;) &#123;<br>       <span class="hljs-keyword">if</span> (need_dfs[Current-&gt;Data])<span class="hljs-comment">//找到仍需被驻扎的节点并存储</span><br>           need_last[++UnsettledNode] = F_length[Current-&gt;Data][<span class="hljs-number">0</span>];<span class="hljs-comment">//值为到根的长度</span><br>       <span class="hljs-keyword">if</span> (Current-&gt;next == <span class="hljs-literal">NULL</span>)<span class="hljs-keyword">break</span>;<br>       <span class="hljs-keyword">else</span> Current = Current-&gt;next;<br>    &#125;<br></code></pre></td></tr></table></figure>

<ol start="8">
<li>最后的匹配<br>这里用到一个贪心策略：对于现在闲置的军队和需要被驻扎的节点，让剩余时间小的军队优先驻扎在距离根节点近的节点，这样可以保证决策最优。匹配过后，若所有需要被驻扎的节点都已有军队驻扎，则说明当前的时限可行；反之则不可行。<br>sort(LeftTime + 1, LeftTime + LeftArmy + 1),<br>sort(need_last + 1, need_last + UnsettledNode + 1); //分别对军队的剩余时间和节点到根节点的距离进行升序排序</li>
</ol>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-type">int</span> i = <span class="hljs-number">1</span>, j = <span class="hljs-number">1</span>;<br><span class="hljs-keyword">while</span> (i &lt;= UnsettledNode &amp;&amp; j &lt;= LeftArmy)<span class="hljs-comment">//扫描整个tim和ned数组 </span><br>&#123;<br>    <span class="hljs-keyword">if</span> (LeftTime[j] &gt;= need_last[i])<span class="hljs-comment">//若可行</span><br>        i++, j++;<span class="hljs-comment">//都扫描到下一位</span><br>    <span class="hljs-keyword">else</span><br>        j++;<span class="hljs-comment">//否则扫描下一支军队</span><br>&#125;<br><br><span class="hljs-keyword">if</span> (i &gt; UnsettledNode)<span class="hljs-comment">//说明所有需要被驻扎的节点都已被驻扎</span><br>    <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;<br><span class="hljs-keyword">else</span><br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br></code></pre></td></tr></table></figure>

<h1 id="八、测试结果："><a href="#八、测试结果：" class="headerlink" title="八、测试结果："></a>八、测试结果：</h1><p>第一组测试数据：<br> <img src="https://imgbed.cheney.cc/picgo/caf9cd5807cc481ea656315f97609189.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p>输出结果：3，符合预期<br> <img src="https://imgbed.cheney.cc/picgo/29a254a29b45451fbb4470172556e58c.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p>第二组测试数据：<br> <img src="https://imgbed.cheney.cc/picgo/f99dd72c39aa4f589b017ec6b75e5778.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p>输出结果：9，符合预期<br> <img src="https://imgbed.cheney.cc/picgo/f83e55e02ccc4b839986d21374f2dd41.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>

            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>
                    
                  </div>
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/%E7%AE%97%E6%B3%95/">算法</a>
                    
                      <a class="hover-with-bg" href="/tags/C/">C++</a>
                    
                      <a class="hover-with-bg" href="/tags/%E6%B4%9B%E8%B0%B7/">洛谷</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">
                  
                    本博客所有文章除特别声明外，均采用 <a target="_blank" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！
                  
                </p>
              
              
                <div class="post-prevnext">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2020/12/02/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%AE%9E%E9%AA%8C--%E8%A1%A8%E8%BE%BE%E5%BC%8F%E7%9A%84%E5%90%8E%E7%BC%80%E8%A1%A8%E7%A4%BA/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">表达式的后缀表示</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div class="toc-body" id="toc-body"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    

    
      <a id="scroll-top-button" aria-label="TOP" href="#" role="button">
        <i class="iconfont icon-arrowup" aria-hidden="true"></i>
      </a>
    

    
      <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
    

    
  </main>

  <footer class="text-center mt-5 py-3">
  <div class="footer-content">
     <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a> <i class="iconfont icon-love"></i> <a href="https://cheney822.gitee.io/" target="_blank" rel="nofollow noopener"><span>备用网址</span></a> 
  </div>
  

  
  <!-- 备案信息 -->
  <div class="beian">
    <span>
      <a href="http://beian.miit.gov.cn/" target="_blank" rel="nofollow noopener">
        皖ICP备2022002876号-1
      </a>
    </span>
    
  </div>


  
</footer>


  <!-- SCRIPTS -->
  
  <script  src="https://cdn.jsdelivr.net/npm/nprogress@0/nprogress.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/nprogress@0/nprogress.min.css" />

  <script>
    NProgress.configure({"showSpinner":false,"trickleSpeed":100})
    NProgress.start()
    window.addEventListener('load', function() {
      NProgress.done();
    })
  </script>


<script  src="https://cdn.jsdelivr.net/npm/jquery@3/dist/jquery.min.js" ></script>
<script  src="https://cdn.jsdelivr.net/npm/bootstrap@4/dist/js/bootstrap.min.js" ></script>
<script  src="/js/events.js" ></script>
<script  src="/js/plugins.js" ></script>

<!-- Plugins -->


  <script  src="/js/local-search.js" ></script>



  
    <script  src="/js/img-lazyload.js" ></script>
  



  



  
    <script  src="https://cdn.jsdelivr.net/npm/tocbot@4/dist/tocbot.min.js" ></script>
  
  
    <script  src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3/dist/jquery.fancybox.min.js" ></script>
  
  
    <script  src="https://cdn.jsdelivr.net/npm/anchor-js@4/anchor.min.js" ></script>
  
  
    <script defer src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js" ></script>
  






  <script  src="https://cdn.jsdelivr.net/npm/typed.js@2/lib/typed.min.js" ></script>
  <script>
    (function (window, document) {
      var typing = Fluid.plugins.typing;
      var title = document.getElementById('subtitle').title;
      
        typing(title);
      
    })(window, document);
  </script>















<!-- 主题的启动项 保持在最底部 -->
<script  src="/js/boot.js" ></script>


</body>
</html>
